

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/Mine.jpg">
  <link rel="icon" href="/img/Mine.jpg">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Chiam">
  <meta name="keywords" content="算法，安全">
  
    <meta name="description" content="『算法-ACM 竞赛-疯子的算法总结』8 最短路算法+模板疯子的算法总结(八) 最短路算法+模板 Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度 O(E+VlgV)BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度 O(VE)SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度 O(kE)，k 为每个节点进入 Que">
<meta property="og:type" content="article">
<meta property="og:title" content="『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板">
<meta property="og:url" content="http://example.com/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E7%96%AF%E5%AD%90%E7%9A%84%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E3%80%8F8%20%E6%9C%80%E7%9F%AD%E8%B7%AF%E7%AE%97%E6%B3%95+%E6%A8%A1%E6%9D%BF/index.html">
<meta property="og:site_name" content="Chiam 的个人主页">
<meta property="og:description" content="『算法-ACM 竞赛-疯子的算法总结』8 最短路算法+模板疯子的算法总结(八) 最短路算法+模板 Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度 O(E+VlgV)BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度 O(VE)SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度 O(kE)，k 为每个节点进入 Que">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20190814092215458.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYyNzExOA==,size_16,color_FFFFFF,t_70">
<meta property="article:published_time" content="2023-12-05T16:11:44.991Z">
<meta property="article:modified_time" content="2023-12-05T16:19:53.079Z">
<meta property="article:author" content="Chiam">
<meta property="article:tag" content="算法，安全">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/20190814092215458.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYyNzExOA==,size_16,color_FFFFFF,t_70">
  
  
  
  <title>『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板 - Chiam 的个人主页</title>

  <link  rel="stylesheet" href="https://lib.baomitu.com/twitter-bootstrap/4.6.1/css/bootstrap.min.css" />



  <link  rel="stylesheet" href="https://lib.baomitu.com/github-markdown-css/4.0.0/github-markdown.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/hint.css/2.7.0/hint.min.css" />

  <link  rel="stylesheet" href="https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.css" />



<!-- 主题依赖的图标库，不要自行修改 -->
<!-- Do not modify the link that theme dependent icons -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_hj8rtnfg7um.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />


  <link id="highlight-css" rel="stylesheet" href="/css/highlight.css" />
  
    <link id="highlight-css-dark" rel="stylesheet" href="/css/highlight-dark.css" />
  



  
<link rel="stylesheet" href="/css/custom.css">



  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    Fluid.ctx = Object.assign({}, Fluid.ctx)
    var CONFIG = {"hostname":"example.com","root":"/","version":"1.9.5-a","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false,"scope":[]},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"left","visible":"hover","icon":"❡"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"code_language":{"enable":true,"default":"TEXT"},"copy_btn":true,"image_caption":{"enable":true},"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"placement":"right","headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":2},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"follow_dnt":true,"baidu":null,"google":{"measurement_id":null},"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml","include_content_in_search":true};

    if (CONFIG.web_analytics.follow_dnt) {
      var dntVal = navigator.doNotTrack || window.doNotTrack || navigator.msDoNotTrack;
      Fluid.ctx.dnt = dntVal && (dntVal.startsWith('1') || dntVal.startsWith('yes') || dntVal.startsWith('on'));
    }
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
  


  
<meta name="generator" content="Hexo 6.3.0"></head>


<body>
  

  <header>
    

<div class="header-inner" style="height: 70vh;">
  <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Chiam&#39;s Blogs</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                
                <span>首页</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                
                <span>归档</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                
                <span>分类</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                
                <span>关于</span>
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                
                <span>友链</span>
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              <i class="iconfont icon-search"></i>
            </a>
          </li>
          
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">
              <i class="iconfont icon-dark" id="color-toggle-icon"></i>
            </a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

  

<div id="banner" class="banner" parallax=true
     style="background: url('/img/default.png') no-repeat center center; background-size: cover;">
  <div class="full-bg-img">
    <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
      <div class="banner-text text-center fade-in-up">
        <div class="h2">
          
            <span id="subtitle" data-typed-text="『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板"></span>
          
        </div>

        
          
  <div class="mt-3">
    
    
      <span class="post-meta">
        <i class="iconfont icon-date-fill" aria-hidden="true"></i>
        <time datetime="2023-12-06 00:11" pubdate>
          2023年12月6日 凌晨
        </time>
      </span>
    
  </div>

  <div class="mt-1">
    
      <span class="post-meta mr-2">
        <i class="iconfont icon-chart"></i>
        
          7.5k 字
        
      </span>
    

    
      <span class="post-meta mr-2">
        <i class="iconfont icon-clock-fill"></i>
        
        
        
          63 分钟
        
      </span>
    

    
    
  </div>


        
      </div>

      
    </div>
  </div>
</div>

</div>

  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="side-col d-none d-lg-block col-lg-2">
      

    </div>

    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div id="board">
          <article class="post-content mx-auto">
            <h1 id="seo-header">『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板</h1>
            
            
              <div class="markdown-body">
                
                <h1 id="『算法-ACM-竞赛-疯子的算法总结』8-最短路算法-模板"><a href="#『算法-ACM-竞赛-疯子的算法总结』8-最短路算法-模板" class="headerlink" title="『算法-ACM 竞赛-疯子的算法总结』8 最短路算法+模板"></a>『算法-ACM 竞赛-疯子的算法总结』8 最短路算法+模板</h1><h1 id="疯子的算法总结-八-最短路算法-模板"><a href="#疯子的算法总结-八-最短路算法-模板" class="headerlink" title="疯子的算法总结(八) 最短路算法+模板"></a>疯子的算法总结(八) 最短路算法+模板</h1><p><img src="https://img-blog.csdnimg.cn/20190814092215458.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYyNzExOA==,size_16,color_FFFFFF,t_70" srcset="/img/loading.gif" lazyload></p>
<p>Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度 O(E+VlgV)<br>BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度 O(VE)<br>SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度 O(kE)，k 为每个节点进入 Queue 的次数，且 k 一般&lt;&#x3D;2，但此处的复杂度证明是有问题的，其实 SPFA 的最坏情况应该是 O(VE).<br>Floyd：每对节点之间的最短路径。</p>
<p>先给出结论：<br>(1)当权值为非负时，用 Dijkstra。<br>(2)当权值有负值，且没有负圈，则用 SPFA，SPFA 能检测负圈，但是不能输出负圈。<br>(3)当权值有负值，而且可能存在负圈，则用 BellmanFord，能够检测并输出负圈。<br>(4)SPFA 检测负环：当存在一个点入队大于等于 V 次，则有负环，后面有证明。</p>
<p>模板就是这些模板，但是这种题通常不会在比赛中单方面考察最短路算法，更多是最短路与图，与环，负环，负权值，连通块等，一同考察，要学会改版子，考虑有向图有环图，有向无环图，没有直接的最短路算法可以解决时，要考虑数据量，然后选择一种最短路，找到合适的改造方法，构造出可以使用该算法的图，进而使用最短路算法，而构造的方法千奇百怪，这绝不是大量练习就能遇到的，而是在练习中寻找一种思考方式，进而能够对陌生题目进行分析，得出合适的解决方案。</p>
<p>学好最短路原理的方法，不是看大牛的讲解，而是自己举一组样例，按照程序的思路去跑一遍，按照他的想法，就能理解算法的设计界原理，比看要记得牢。</p>
<p>BFS 相关：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43627118/article/details/100088087">https://blog.csdn.net/weixin_43627118/article/details/100088087</a></p>
<p>DFS 相关：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43627118/article/details/100107848">https://blog.csdn.net/weixin_43627118/article/details/100107848</a></p>
<p>floyd 技巧：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43627118/article/details/100129268">https://blog.csdn.net/weixin_43627118/article/details/100129268</a></p>
<p>超级源点&amp;汇点：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43627118/article/details/100134565">https://blog.csdn.net/weixin_43627118/article/details/100134565</a></p>
<p>链式前向星（边集数组）：<a target="_blank" rel="noopener" href="https://mp.csdn.net/postedit/99612887">https://mp.csdn.net/postedit/99612887</a></p>
<h2 id="Floyd-算法戳这里：https-blog-csdn-net-weixin-43627118-article-details-90387061"><a href="#Floyd-算法戳这里：https-blog-csdn-net-weixin-43627118-article-details-90387061" class="headerlink" title="Floyd 算法戳这里：https://blog.csdn.net/weixin_43627118/article/details/90387061"></a>Floyd 算法戳这里：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43627118/article/details/90387061">https://blog.csdn.net/weixin_43627118/article/details/90387061</a></h2><pre><code class="hljs">//最基础的Dijkstra，用于理解算法本质原理，适用的类型于队列优化的一样，但是时间复杂度太高，所以，用的比较少。
#include&lt;iostream&gt;
#include&lt;queue&gt;
#include&lt;algorithm&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;bitset&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf(&quot;%d&quot;,&amp;n)
#define cinl(n) scanf(&quot;%lld&quot;,&amp;n)
#define cinc(n) scanf(&quot;%c&quot;,&amp;n)
#define cins(s) scanf(&quot;%s&quot;,s)
#define coui(n) printf(&quot;%d&quot;,n)
#define couc(n) printf(&quot;%c&quot;,n)
#define coul(n) printf(&quot;%lld&quot;,n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a&gt;b?a:b
#define Min(a,b) a&lt;b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=1e3+10;
const double esp=1e-9;
//-------------------------------------------------------//

int n,m; //n个节点，m条边
int dis[maxn][maxn];
bool vis[maxn];
int d[maxn];
inline void dijstra();
int main()
&#123;
    mem(dis,0x3f);
    mem(vis,0);
    mem(d,0x3f);
    for(int i=1; i&lt;=n; i++)dis[i][i]=0;
    cini(m),cini(n);//输入边数//点数
    for(int i=0; i&lt;m; i++)
    &#123;
        int x,y,z;
        cini(x),cini(y),cini(z);
        dis[x][y]=min(dis[x][y],z);
        dis[y][x]=min(dis[y][x],z);
        //cout&lt;&lt;dis[x][y]&lt;&lt;endl;
    &#125;
    dijstra();
    cout&lt;&lt;d[n]&lt;&lt;endl;
&#125;
inline void dijstra()
&#123;
    d[1]=0;
    for(int i=1; i&lt;=n; i++)
    &#123;
        int x=0;
        for(int j=1; j&lt;=n; j++)
            if(!vis[j]&amp;&amp;(d[j]&lt;d[x]||x==0))x=j;

        vis[x]=1;
        for(int j=1;j&lt;=n;j++)
            d[j]=min(d[j],d[x]+dis[x][j]);

    &#125;
&#125;



#include&lt;iostream&gt;
#include&lt;queue&gt;
#include&lt;algorithm&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;bitset&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf(&quot;%d&quot;,&amp;n)
#define cinl(n) scanf(&quot;%lld&quot;,&amp;n)
#define cinc(n) scanf(&quot;%c&quot;,&amp;n)
#define cins(s) scanf(&quot;%s&quot;,s)
#define coui(n) printf(&quot;%d&quot;,n)
#define couc(n) printf(&quot;%c&quot;,n)
#define coul(n) printf(&quot;%lld&quot;,n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a&gt;b?a:b
#define Min(a,b) a&lt;b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define INF  0x3f3f3f3f
#define maxn  100010
#define esp  1e-9
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
//-----------------------*******----------------------------//

int next[maxn*10],ege[maxn*10],head[maxn],ver[maxn*10],d[maxn];
bool vis[maxn];
int tot=0;
void add(int x,int y,int z) //аз╫с╠М
&#123;
    ege[++tot]=z;
    next[tot]=head[x];
    head[x]=tot;
    ver[tot]=y;
        //有向图建一条边，无向图反向建边
   // ege[++tot]=z;
   // next[tot]=head[y];
   // head[y]=tot;
   // ver[tot]=x;
&#125;
int n,m;
inline void dijkstra();
int main()
&#123;
    mem(vis,0);
    mem(d,0x3f);
    cini(m);
    cini(n);
    for(int i=0; i&lt;m; i++)
    &#123;
        int x,y,z;
        cini(x),cini(y),cini(z);
        add(x,y,z);
    &#125;
    dijkstra();
    cout&lt;&lt;d[n]&lt;&lt;endl;
&#125;
inline void dijkstra()
&#123;
    d[1]=0;
    priority_queue&lt;pair&lt;int,int&gt; &gt;qu;
    while(qu.size())
        qu.pop();
    qu.push(mp(0,1));
    while(qu.size())
    &#123;
        //cout&lt;&lt;qu.size()&lt;&lt;endl;
        int x=qu.top().second;
        qu.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=head[x]; i; i=next[i])
        &#123;
            int y=ver[i],z=ege[i];
            if(d[y]&gt;=d[x]+z)
            &#123;
                d[y]=d[x]+z;
                qu.push(mp(-d[y],y));
            &#125;

        &#125;
    &#125;
&#125;



//Ford 算法有一点DP的思想，同样的松弛操作，但是时间复杂度略高
#define _CRT_SECURE_NO_WARNINGS
#include&lt;iostream&gt;
#include&lt;queue&gt;
#include&lt;algorithm&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;bitset&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf(&quot;%d&quot;,&amp;n)
#define cinl(n) scanf(&quot;%lld&quot;,&amp;n)
#define cinc(n) scanf(&quot;%c&quot;,&amp;n)
#define cins(s) scanf(&quot;%s&quot;,s)
#define coui(n) printf(&quot;%d&quot;,n)
#define couc(n) printf(&quot;%c&quot;,n)
#define coul(n) printf(&quot;%lld&quot;,n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a&gt;b?a:b
#define Min(a,b) a&lt;b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define INF  0x3f3f3f3f
#define maxn  100010
#define esp  1e-9
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
//-----------------------*******----------------------------//
int n,m;
int ege[maxn*10],head[maxn],later[maxn*10],dis[maxn];
bool vis[maxn];
inline bool ford()
&#123;
    mem(vis,0);
    mem(dis,0x3f);
    vis[1]=1;
    dis[1]=0;
    for(int i=1; i&lt;n; i++) //n-1´ÎÑ­»·
    &#123;
        int check=1;
        for(int j=1; j&lt;=m; j++)
        &#123;
            if(vis[head[j]]||vis[later[j]])
            &#123;
                if(dis[head[j]]+ege[j]&lt;dis[later[j]])
                &#123;
                    dis[later[j]] =dis[head[j]]+ege[j];
                    vis[later[j]]=1;
                    check=0;
                &#125;
                if(dis[later[j]]+ege[j]&lt;dis[head[j]])//有向图，不用反向松弛
                &#123;
                    dis[head[j]] =dis[later[j]]+ege[j];
                    vis[head[j]]=1;
                    check=0;
                &#125;
            &#125;
        &#125;
        if(check)
            break;
    &#125;
    for(int i=1; i&lt;m; i++)
        if(dis[head[i]]+ege[i]&lt;dis[later[i]])
            return 1;
    return 0;
&#125;
int main()
&#123;
    cini(m),cini(n);
    for(int i=1; i&lt;=m; i++)
    &#123;
        cini(head[i]);
        cini(later[i]);
        cini(ege[i]);
    &#125;
    ford();
    cout&lt;&lt;dis[n];
&#125;



SPFA，是队列优化的ford算法
#include&lt;iostream&gt;
#include&lt;queue&gt;
#include&lt;algorithm&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;bitset&gt;
#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#define Swap(a,b) a^=b^=a^=b
#define cini(n) scanf(&quot;%d&quot;,&amp;n)
#define cinl(n) scanf(&quot;%lld&quot;,&amp;n)
#define cinc(n) scanf(&quot;%c&quot;,&amp;n)
#define cins(s) scanf(&quot;%s&quot;,s)
#define coui(n) printf(&quot;%d&quot;,n)
#define couc(n) printf(&quot;%c&quot;,n)
#define coul(n) printf(&quot;%lld&quot;,n)
#define speed ios_base::sync_with_stdio(0)
#define Max(a,b) a&gt;b?a:b
#define Min(a,b) a&lt;b?a:b
#define mem(n,x) memset(n,x,sizeof(n))
#define INF  0x3f3f3f3f
#define maxn  100010
#define esp  1e-9
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
//-----------------------*******----------------------------//
int next[maxn*10],ege[maxn*10],head[maxn],ver[maxn*10],d[maxn];
bool vis[maxn];
int tot=0,n,m;
void add(int x,int y,int z)
&#123;
    next[++tot]=head[x];
    ege[tot]=z;
    ver[tot]=y;
    head[x]=tot;
    next[++tot]=head[y];
    ege[tot]=z;
    ver[tot]=x;
    head[y]=tot;
&#125;
void spfa(int w)
&#123;
    mem(d,0x3f);
    mem(vis,0);
    vis[w]=1;
    d[w]=0;
    queue&lt;int&gt; q;
    while(q.size()) q.pop();
    q.push(w);
    while(q.size())
    &#123;
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=next[i])
        &#123;
            int y=ver[i],z=ege[i];
            if(d[y]&gt;d[x]+z)
            &#123;
                d[y]=d[x]+z;
                if(!vis[y]) q.push(y),vis[y]=1;
            &#125;
        &#125;
    &#125;
&#125;
int main()
&#123;
    cini(m);
    cini(n);
    for(int i=0; i&lt;m; i++)
    &#123;
        int x,y,z;
        cini(x),cini(y),cini(z);
        add(x,y,z);
    &#125;
    int w;
    cin&gt;&gt;w;
    spfa(w);
    for(int i=1;i&lt;=n;i++)
    cout&lt;&lt;d[i]&lt;&lt;endl;
&#125;
</code></pre>

                
              </div>
            
            <hr/>
            <div>
              <div class="post-metas my-3">
  
    <div class="post-meta mr-3 d-flex align-items-center">
      <i class="iconfont icon-category"></i>
      

<span class="category-chains">
  
  
    
      <span class="category-chain">
        
  <a href="/categories/%E7%AE%97%E6%B3%95/" class="category-chain-item">算法</a>
  
  
    <span>></span>
    
  <a href="/categories/%E7%AE%97%E6%B3%95/ACM%E7%AB%9E%E8%B5%9B/" class="category-chain-item">ACM竞赛</a>
  
  
    <span>></span>
    
  <a href="/categories/%E7%AE%97%E6%B3%95/ACM%E7%AB%9E%E8%B5%9B/%E7%96%AF%E5%AD%90%E7%9A%84%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/" class="category-chain-item">疯子的算法总结</a>
  
  

  

  

      </span>
    
  
</span>

    </div>
  
  
</div>


              
  

  <div class="license-box my-3">
    <div class="license-title">
      <div>『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板</div>
      <div>http://example.com/2023/12/06/『算法-ACM竞赛-疯子的算法总结』8 最短路算法+模板/</div>
    </div>
    <div class="license-meta">
      
        <div class="license-meta-item">
          <div>作者</div>
          <div>Chiam</div>
        </div>
      
      
        <div class="license-meta-item license-meta-date">
          <div>发布于</div>
          <div>2023年12月6日</div>
        </div>
      
      
      
        <div class="license-meta-item">
          <div>许可协议</div>
          <div>
            
              
              
                <a class="print-no-link" target="_blank" href="https://creativecommons.org/licenses/by/4.0/">
                  <span class="hint--top hint--rounded" aria-label="BY - 署名">
                    <i class="iconfont icon-by"></i>
                  </span>
                </a>
              
            
          </div>
        </div>
      
    </div>
    <div class="license-icon iconfont"></div>
  </div>



              
                <div class="post-prevnext my-3">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E7%96%AF%E5%AD%90%E7%9A%84%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E3%80%8F9.1%20%20%E5%9B%BE%E8%AE%BA%E4%B8%AD%E7%9A%84%E7%9F%A9%E9%98%B5%E5%BA%94%E7%94%A8Part1POJ3613CowRelays/" title="『算法-ACM竞赛-疯子的算法总结』9.1  图论中的矩阵应用Part1POJ3613CowRelays">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">『算法-ACM竞赛-疯子的算法总结』9.1  图论中的矩阵应用Part1POJ3613CowRelays</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2023/12/06/%E3%80%8E%E7%AE%97%E6%B3%95-ACM%E7%AB%9E%E8%B5%9B-%E7%96%AF%E5%AD%90%E7%9A%84%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E3%80%8F7%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95%E4%B9%8B%20%20manacher%20%E7%AE%97%E6%B3%95%20O%EF%BC%88N%EF%BC%89%E8%A7%A3%E5%86%B3%E5%9B%9E%E6%96%87%E4%B8%B2/" title="『算法-ACM竞赛-疯子的算法总结』7字符串算法之  manacher 算法 O（N）解决回文串">
                        <span class="hidden-mobile">『算法-ACM竞赛-疯子的算法总结』7字符串算法之  manacher 算法 O（N）解决回文串</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
  
  
    <article id="comments" lazyload>
      
  <div id="valine"></div>
  <script type="text/javascript">
    Fluid.utils.loadComments('#valine', function() {
      Fluid.utils.createScript('https://lib.baomitu.com/valine/1.5.1/Valine.min.js', function() {
        var options = Object.assign(
          {"appId":"fIfc7WqUDZohlQuPc2lz5mJy-MdYXbMMI","appKey":"zjlAG3ZA3o4cBHVAkjzc2Z20","path":"window.location.pathname","placeholder":"留言仅限讨论，禁止广告等行为","avatar":"retro","meta":["nick","mail","link"],"requiredFields":[],"pageSize":10,"lang":"zh-CN","highlight":false,"recordIP":false,"serverURLs":"https://fifc7wqu.api.lncldglobal.com","emojiCDN":null,"emojiMaps":null,"enableQQ":false},
          {
            el: "#valine",
            path: window.location.pathname
          }
        )
        new Valine(options);
        Fluid.utils.waitElementVisible('#valine .vcontent', () => {
          var imgSelector = '#valine .vcontent img:not(.vemoji)';
          Fluid.plugins.imageCaption(imgSelector);
          Fluid.plugins.fancyBox(imgSelector);
        })
      });
    });
  </script>
  <noscript>Please enable JavaScript to view the comments</noscript>


    </article>
  


          </article>
        </div>
      </div>
    </div>

    <div class="side-col d-none d-lg-block col-lg-2">
      
  <aside class="sidebar" style="margin-left: -1rem">
    <div id="toc">
  <p class="toc-header">
    <i class="iconfont icon-list"></i>
    <span>目录</span>
  </p>
  <div class="toc-body" id="toc-body"></div>
</div>



  </aside>


    </div>
  </div>
</div>





  



  



  



  



  







    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v" for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>

    

    
  </main>

  <footer>
    <div class="footer-inner">
  
    <div class="footer-content">
       <meta name="referrer" content="no-referrer" /> <footer id="footer" role="contentinfo"> <div class="divider"> <div class="wall"></div> <img class="animals" src="/img/footer_animals_new.png" srcset="/img/loading.gif" lazyload alt="Footer Animals"> </div> <div class="container" data-index="450"> <p> <a href="https://chiamzhang.github.io" target="_blank">DogEgg</a> <i class="iconfont icon-love"></i> <a href="#" target="_blank">LittePig</a> </p> <p> Powered by  <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-pen"></i> Theme  <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a> </p> </div> </footer> 
    </div>
  
  
  
  
</div>

  </footer>

  <!-- Scripts -->
  
  <script  src="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://lib.baomitu.com/jquery/3.6.4/jquery.min.js" ></script>
<script  src="https://lib.baomitu.com/twitter-bootstrap/4.6.1/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>


  <script  src="https://lib.baomitu.com/typed.js/2.0.12/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var subtitle = document.getElementById('subtitle');
      if (!subtitle || !typing) {
        return;
      }
      var text = subtitle.getAttribute('data-typed-text');
      
        typing(text);
      
    })(window, document);
  </script>




  
    <script  src="/js/img-lazyload.js" ></script>
  




  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/tocbot/4.20.1/tocbot.min.js', function() {
    var toc = jQuery('#toc');
    if (toc.length === 0 || !window.tocbot) { return; }
    var boardCtn = jQuery('#board-ctn');
    var boardTop = boardCtn.offset().top;

    window.tocbot.init(Object.assign({
      tocSelector     : '#toc-body',
      contentSelector : '.markdown-body',
      linkClass       : 'tocbot-link',
      activeLinkClass : 'tocbot-active-link',
      listClass       : 'tocbot-list',
      isCollapsedClass: 'tocbot-is-collapsed',
      collapsibleClass: 'tocbot-is-collapsible',
      scrollSmooth    : true,
      includeTitleTags: true,
      headingsOffset  : -boardTop,
    }, CONFIG.toc));
    if (toc.find('.toc-list-item').length > 0) {
      toc.css('visibility', 'visible');
    }

    Fluid.events.registerRefreshCallback(function() {
      if ('tocbot' in window) {
        tocbot.refresh();
        var toc = jQuery('#toc');
        if (toc.length === 0 || !tocbot) {
          return;
        }
        if (toc.find('.toc-list-item').length > 0) {
          toc.css('visibility', 'visible');
        }
      }
    });
  });
</script>


  <script src=https://lib.baomitu.com/clipboard.js/2.0.11/clipboard.min.js></script>

  <script>Fluid.plugins.codeWidget();</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/anchor-js/4.3.1/anchor.min.js', function() {
    window.anchors.options = {
      placement: CONFIG.anchorjs.placement,
      visible  : CONFIG.anchorjs.visible
    };
    if (CONFIG.anchorjs.icon) {
      window.anchors.options.icon = CONFIG.anchorjs.icon;
    }
    var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
    var res = [];
    for (var item of el) {
      res.push('.markdown-body > ' + item.trim());
    }
    if (CONFIG.anchorjs.placement === 'left') {
      window.anchors.options.class = 'anchorjs-link-left';
    }
    window.anchors.add(res.join(', '));

    Fluid.events.registerRefreshCallback(function() {
      if ('anchors' in window) {
        anchors.removeAll();
        var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
        var res = [];
        for (var item of el) {
          res.push('.markdown-body > ' + item.trim());
        }
        if (CONFIG.anchorjs.placement === 'left') {
          anchors.options.class = 'anchorjs-link-left';
        }
        anchors.add(res.join(', '));
      }
    });
  });
</script>


  
<script>
  Fluid.utils.createScript('https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.js', function() {
    Fluid.plugins.fancyBox();
  });
</script>


  <script>Fluid.plugins.imageCaption();</script>

  <script  src="/js/local-search.js" ></script>




  
<script src="/js/love.js"></script>
<script src="/js/funnyTitle.js"></script>
<script src="/js/backTop.js"></script>
<script src="//cdn.jsdelivr.net/gh/bynotes/texiao/source/js/xiaoxuehua.js"></script>



<!-- 主题的启动项，将它保持在最底部 -->
<!-- the boot of the theme, keep it at the bottom -->
<script  src="/js/boot.js" ></script>


  

  <noscript>
    <div class="noscript-warning">博客在允许 JavaScript 运行的环境下浏览效果更佳</div>
  </noscript>
<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/wanko.model.json"},"display":{"position":"left","width":150,"height":150,"hOffset":20,"vOffset":0},"mobile":{"show":false,"scale":0.5},"react":{"opacity":0.9},"log":false});</script></body>
</html>
